package leetcode_21_40;

import java.util.ArrayList;
import java.util.List;

public class generateParenthesis_22 {
    /**
     * 括号生成
     * 数字 n 代表生成括号的对数，用于能够生成所有可能的并且 有效的 括号组合。
     * 思路是计算实时的左右括号数
     * 左括号必须大于等于右括号
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        function("(", 0, 2 * n);
        return ans;
    }

    public static int l = 0, r = 0;      //实时的左右括号数
    public static List<String> ans = new ArrayList<>();
    public static StringBuilder b = new StringBuilder();

    public static void function(String s, int index, int len) {
        if (l == r && s.equals(")")) {   //当左右括号数量相等，下一个就不可能再是 ）
            b.append("a");         //避免无法剪切
            r++;
            return;
        }
        b.append(s);
        if (s.equals("(")) l++;
        else r++;
        if (l < len / 2) {
            function("(", index + 1, len);
            if(b.charAt(b.length()-1)=='(')
                l--;
            else r--;
            b.deleteCharAt(b.length() - 1);//关键一步，上一层递归结束，需要遍历下一个字母，
            //此时删除公共字符串上一次尾部添加的字符，添加新的字符
        }
        if(index == len - 1){                                      //放在这里进行判断是因为最后一位肯定是）
                                                                                //并且防止多余的一层递归多剪切一层字符
            ans.add(b.toString());
            return;
        }
        function(")", index + 1, len);
        if(b.charAt(b.length()-1)=='(')
            l--;
        else r--;
        b.deleteCharAt(b.length() - 1);
    }
}
